#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;
/*6247. 从链表中移除节点 显示英文描述
通过的用户数521
尝试过的用户数546
用户总通过次数522
用户总提交次数567
题目难度Medium
给你一个链表的头节点 head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。

返回修改后链表的头节点 head 。



示例 1：



输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
示例 2：

输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。*/

//尝试递归解决 返回移除后的头节点
ListNode *removeNodes_r(ListNode *head) {
    if (head == nullptr || !head->next)
        return head;


    auto res = removeNodes(head->next);
    //删除节点
    if (head->next->val > head->val)
        head = res;
    else
        head->next = res;


    return head;

}


ListNode *removeNodes(ListNode *head) {
    if (head == nullptr || !head->next)
        return head;


    auto res = removeNodes_r(head);
    if (res && res->next && res->next->val > res->val)
        return res->next;


    return res;

}